package exercise;

import java.util.*;

public class LC_692 {
    public static void main(String[] args) {
        String[] words = {"a", "b", "e", "a", "c", "e", "a", "a", "e", "c", "c", "e"};
        List<String> s = topKFrequent(words,3);
        System.out.println(s);
    }
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> hashMap = new HashMap<>();
        // 1. 统计每个单词出现的次数
        for (String s : words) {
            if(hashMap.get(s) == null){
                hashMap.put(s,1);
            } else {
                hashMap.put(s,hashMap.get(s) + 1);
            }
        }
        // 2. 建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){   // 如果出现次数相同
                    return o2.getKey().compareTo(o1.getKey());  // 将字典序大的放在前面
                }
                return o1.getValue().compareTo(o2.getValue());  // 小根堆
            }
        });
        // 3. 遍历hashMap 把里面的数据放到小根堆
        for (Map.Entry<String,Integer> entry : hashMap.entrySet()) {
            if(minHeap.size() < k){
                minHeap.add(entry);  //  先让小根堆放k个
            } else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0 ){  // entry中出现次数更多
                    minHeap.poll();                                   // 则弹出一个，再入堆
                    minHeap.add(entry);
                } else if(top.getValue().compareTo(entry.getValue()) == 0){  // 如果次数一样多
                    if(top.getKey().compareTo(entry.getKey()) > 0){  // 单词顺序 a<b  a在b前面
                        minHeap.poll();
                        minHeap.add(entry);
                    }
                }
            }
        }
        // 4. 此时小根堆中已经有结果 逆置
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String s = minHeap.poll().getKey();
            list.add(s);
        }
        Collections.reverse(list);
        return list;
    }
}
